"""
§8.3 线段树（无区间更新）
线段树本质是二叉树，在学习之前，建议先做做 104. 二叉树的最大深度 和 111. 二叉树的最小深度（自底向上写法），当作热身。

线段树：为什么要这样设计？ 理解线段树发明的动机。

把任意区间用 O(logn) 个区间表示，线段树的每个节点记录对应区间的信息。

询问：把询问区间拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点，把这 O(logn) 个节点的信息合并，即为答案。
单点更新：有 O(logn) 个区间包含被修改的位置，需要更新 O(logn) 个节点的信息。
基础模板代码如下。为方便入门理解，我没有做复杂封装。通用模板代码可以参考 AtCoder Library 的 segtree.hpp。

作者：灵茶山艾府
链接：https://leetcode.cn/discuss/post/3583665/fen-xiang-gun-ti-dan-chang-yong-shu-ju-j-bvmv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
from typing import List


# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
# 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
# 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
# 区间的下标：从 0 开始
class SegmentTree:
    def __init__(self, arr, default=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
        # arr 可以是 list 或者 int
        # 如果 arr 是 int，视作数组大小，默认值为 default
        if isinstance(arr, int):
            arr = [default] * arr
        n = len(arr)
        self._n = n
        self._tree = [0] * (2 << (n - 1).bit_length())
        self._build(arr, 1, 0, n - 1)
        print(self._tree)

    # 合并两个 val
    def _merge_val(self, a: int, b: int) -> int:
        return max(a, b)  # **根据题目修改**

    # 合并左右儿子的 val 到当前节点的 val
    def _maintain(self, node: int) -> None:
        self._tree[node] = self._merge_val(self._tree[node * 2], self._tree[node * 2 + 1])

    # 用 a 初始化线段树
    # 时间复杂度 O(n)
    def _build(self, a: List[int], node: int, l: int, r: int) -> None:
        if l == r:  # 叶子
            self._tree[node] = a[l]  # 初始化叶节点的值
            return
        m = (l + r) // 2
        self._build(a, node * 2, l, m)  # 初始化左子树
        self._build(a, node * 2 + 1, m + 1, r)  # 初始化右子树
        self._maintain(node)

    def _update(self, node: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:  # 叶子（到达目标）
            # 如果想直接替换的话，可以写 self._tree[node] = val
            self._tree[node] = self._merge_val(self._tree[node], val)
            return
        m = (l + r) // 2
        if i <= m:  # i 在左子树
            self._update(node * 2, l, m, i, val)
        else:  # i 在右子树
            self._update(node * 2 + 1, m + 1, r, i, val)
        self._maintain(node)

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        """
        寻找ql,qr区间的最大值(未实现找第一个>=x的功能)，node,l,r只是内部递归使用，不作为传参
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :return:
        """
        #不一定需要完全遍历到叶子节点，比如当前计算的是数组的最大值，比如[3,4,1]那么直接首次返回顶点4即可，不需要遍历到叶子，因为4下面的所有叶子都包含在[ql,qr]
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内，返回当前的就是最大值
            return self._tree[node]
        m = (l + r) // 2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._query(node * 2, l, m, ql, qr)
        #分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._query(node * 2 + 1, m + 1, r, ql, qr)
        #左右树都存在寻找的位置，找个最大的
        l_res = self._query(node * 2, l, m, ql, qr)
        r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
        return self._merge_val(l_res, r_res)

    def _querFirstLarge(self, node: int, l: int, r: int, ql: int, qr: int,target: int) -> int:
        """
        找到ql,qr区间第一个>=target的数
        :param node:
        :param l:
        :param r:
        :param ql:
        :param qr:
        :param target:
        :return:
        """
        #如果当前最大还小，直接返回
        if self._tree[node]<=target:
            return -1
        #遍历到叶子节点
        if l==r:
            # self._tree[node] = -1 #如果不能重复拿同一个数字，则赋值-1
            return l
        m = (l+r)//2
        #分了一半，但是发现要查找的元素全在左边
        if qr <= m:  # [ql, qr] 在左子树
            return self._querFirstLarge(node * 2, l, m, ql, qr, target)
            # 分了一半，但是发现要查找的元素全在右
        if ql > m:  # [ql, qr] 在右子树
            return self._querFirstLarge(node * 2 + 1, m + 1, r, ql, qr, target)
            # 优先找左边,如果左边找得到就不需要找右边了
        res = self._querFirstLarge(node * 2, l, m, ql, qr, target)
        if res == -1:
            # 左边没找到找右边
            res = self._querFirstLarge(node * 2 + 1, m + 1, r, ql, qr, target)
        #如果不能重复拿同一个数字,则需要更新当前的最大值
        # self._maintain(node)
        return res

    # 更新 a[i] 为 _merge_val(a[i], val)
    # 时间复杂度 O(log n)
    def update(self, i: int, val: int) -> None:
        self._update(1, 0, self._n - 1, i, val)

    # 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    # 时间复杂度 O(log n)
    def query(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self._n - 1, ql, qr)

    # 获取 a[i] 的值
    # 时间复杂度 O(log n)
    def get(self, i: int) -> int:
        return self._query(1, 0, self._n - 1, i, i)

if __name__ == '__main__':
    # s = SegmentTree([5, 4, 3, 4, 7, 9, 8, 4])
    # print(s.query(0,2))
    s = SegmentTree([9,9,9,9,9])
    print(s.query(0,1))
    s = SegmentTree([9, 9, 9, 9, 9, 0, 0, 0])
